package code;

public class Code86 {
	
	
    public ListNode partition(ListNode head, int x) {
    	ListNode p,q,lessPre,nt;
    	p=head;
    	if(head==null)
    		return head;
    	lessPre=null;
    	q=null;
    	nt=null;
    	while(p!=null){
    		ListNode tmp=p.next;
    		if(p.val<x){
    			if(lessPre==null){
    				head=p;
    				lessPre=p;
    				lessPre.next=null;
    			}
    			else{
	    			lessPre.next=p;
	    			lessPre=lessPre.next;
	    			lessPre.next=null;
    			}
    		}
    		else{
    			if(q==null){
    				nt=p;
    				q=p;
    				q.next=null;
    			}
    			else{
	    			q.next=p;
	    			q=q.next;
	    			q.next=null;
    			}
    		}
    		p=tmp;
    	}
    	if(lessPre!=null){
    		lessPre.next=nt;
    		return head;
    	}
    	return nt;
    }
	public static void main(String[] args){
		ListNode x1=new ListNode(1);
		ListNode x2=new ListNode(2);
		ListNode x3=new ListNode(3);
		ListNode x4=new ListNode(4);
		ListNode x5=new ListNode(5);
		x2.next=x1;
//		x4.next=x3;
//		x3.next=x2;
//		x2.next=x5;
		
		Code86 code=new Code86();
		ListNode head=code.partition(x2, 2);
		ListNode p=head;
		while(p!=null){
			System.out.println(p.val);
			p=p.next;
		}
		
	}
}
